using System;

namespace Arbol
{

	public class FPtree : TotalSupportTree
	{

		/* ------ FIELDS ------ */

		/// <summary>
		/// FP-tree node structure comprising a <TT>FPgrowthItemPrefixSubtreeNode</TT> in 
		/// which to store counts and a reference to a child branch. 
		/// </summary>

		public class FPtreeNode
		{
			public readonly FPtree outerInstance;

			/// <summary>
			/// The FP tree node. </summary>
			public FPgrowthItemPrefixSubtreeNode node = null;
		/// <summary>
		/// The reference to the child branch (levels in FP-tree branches are
		/// stored as a arrays of <TT>FPtreeNode</TT> structures. 
		/// </summary>
			public FPtreeNode[] childRefs = null;

		/// <summary>
		/// Default constructor. </summary>

		protected internal FPtreeNode(FPtree outerInstance)
		{
			this.outerInstance = outerInstance;
		}

		/// <summary>
		/// Single argument constructor. </summary>
		/// <param name="newNode"> the reference to a new node to be included in the
		/// FP-tree. </param>

		public FPtreeNode(FPtree outerInstance, FPgrowthItemPrefixSubtreeNode newNode)
		{
			this.outerInstance = outerInstance;
			node = newNode;
		}
		}

		/// <summary>
		/// Prefix subtree structure. <P> A set enumeration tree in which to store
		/// itemsets together with support values. 
		/// </summary>

		public class FPgrowthItemPrefixSubtreeNode
		{
			private readonly FPtree outerInstance;

			/// <summary>
			/// The attribute identifier. </summary>
			internal short itemName;
		/// <summary>
		/// The support count. </summary>
		internal int itemCount;
		/// <summary>
		/// The backward link to the parent node in FP tree. </summary>
		internal FPgrowthItemPrefixSubtreeNode parentRef = null;
		/// <summary>
		/// The forward link to the next node in a linked list of nodes with
		/// same attribute identifier starting with an element in the header table
		/// (array). 
		/// </summary>
		internal FPgrowthItemPrefixSubtreeNode nodeLink = null;

		/// <summary>
		/// Default constructor. </summary>

		internal FPgrowthItemPrefixSubtreeNode(FPtree outerInstance)
		{
			this.outerInstance = outerInstance;
		}

		/// <summary>
		/// Three argument constructor. </summary>
		/// <param name="name"> the itemset identifier. </param>
		/// <param name="support"> the support value for the itemset. </param>
		/// <param name="backRef"> the backward link to the parent node.  </param>

		internal FPgrowthItemPrefixSubtreeNode(FPtree outerInstance, short name, int support, FPgrowthItemPrefixSubtreeNode backRef)
		{
			this.outerInstance = outerInstance;
			itemName = name;
			itemCount = support;
			parentRef = backRef;
		}
		}

		/// <summary>
		/// Header table. <P> Array of these structures used to link into FP-tree.
		/// All FP-tree nodes with the same identifier are linked together starting
		/// from a node in a header table (made up of <TT>HeaderTasble</TT> structures).
		/// It is this "cross" linking that gives the FP-tree its most significant
		/// advantage. 
		/// </summary>

		public class FPgrowthHeaderTable
		{
			private readonly FPtree outerInstance;

			/// <summary>
			/// The 1-itemset (attribute) identifier. </summary>
		protected internal short itemName;
		/// <summary>
		/// The forward link to the next node in the link list of nodes. </summary>
			public FPgrowthItemPrefixSubtreeNode nodeLink = null;

		// Constructors

		public FPgrowthHeaderTable(FPtree outerInstance, short columnNum)
		{
			this.outerInstance = outerInstance;
			itemName = columnNum;
		}
		}

		/// <summary>
		/// Structure in which to store ancestor itemSets, i.e. nodes in an FP-tree
		/// that preceed the nodes identified by following a trail of links from a
		/// particular item in the header table. 
		/// </summary>

		private class FPgrowthSupportedSets
		{
			private readonly FPtree outerInstance;

			/// <summary>
			/// The itemSet label. </summary>
			internal short[] itemSet = null;
		/// <summary>
		/// The associated support value for the given itemset. </summary>
			internal int support;
		/// <summary>
		/// The reference to the next node in a linked list. </summary>
		internal FPgrowthSupportedSets nodeLink = null;

		/// <summary>
		/// Three argument constructor. </summary>
		/// <param name="newitemSet"> the given itemSet label. </param>
		/// <param name="newSupport"> the associated support value for the given itemset. </param>
		/// <param name="newNodeLink"> the reference to the next node in a linked list.  </param>

		internal FPgrowthSupportedSets(FPtree outerInstance, short[] newitemSet, int newSupport, FPgrowthSupportedSets newNodeLink)
		{
			this.outerInstance = outerInstance;
			itemSet = newitemSet;
				support = newSupport;
			nodeLink = newNodeLink;
		}
		}

		/// <summary>
		/// Structure in which to store counts. </summary>

		private class FPgrowthColumnCounts
		{
			private readonly FPtree outerInstance;

			/// <summary>
			/// The column/attribute ID number. </summary>
			internal short columnNum;
		/// <summary>
		/// The associated support value. </summary>
			internal int support = 0;

		/// <summary>
		/// One argument constructor. </summary>
		/// <param name="column"> the column/attribute ID number.  </param>

		internal FPgrowthColumnCounts(FPtree outerInstance, int column)
		{
			this.outerInstance = outerInstance;
			columnNum = (short) column;
		}

		/// <summary>
		/// Two argument constructor. </summary>
		/// <param name="column"> the column/attribute ID number. </param>
		/// <param name="sup"> the associatec support value.  </param>

		internal FPgrowthColumnCounts(FPtree outerInstance, int column, int sup)
		{
			this.outerInstance = outerInstance;
			columnNum = (short) column;
			support = sup;
		}
		}

		// Data structures

		/// <summary>
		/// Start reference for FP-tree. </summary>
		protected internal FPtreeNode rootNode = null;
		/// <summary>
		/// Start reference for header table. </summary>
		protected internal FPgrowthHeaderTable[] headerTable;
		/// <summary>
		/// Start reference for supportedSets linked list (temporary storage 
		/// only).
		/// </summary>
		private static FPgrowthSupportedSets startTempSets = null;

		// Other fields 

		/// <summary>
		/// Temporary storage for an index into an array of FP-tree nodes. </P>
		/// Used when reassigning child reference arrays. 
		/// </summary>
		private int tempIndex = 0;
		/// <summary>
		/// Number of nodes created. </summary>
		private int numberOfNodes;

		/* ------ CONSTRUCTORS ------ */

		/// <summary>
		/// Constructor to process command line argument. </summary>
		/// <param name="args"> the command line arguments.  </param>

		public FPtree(string[] args) : base(args)
		{

		// Initialise root node
		rootNode = new FPtreeNode(this);

		// Create header table	
		headerTable = new FPgrowthHeaderTable[numOneItemSets + 1];

		// Populate header table	
		for (int index = 1;index < headerTable.Length;index++)
		{
			headerTable[index] = new FPgrowthHeaderTable(this, (short) index);
		}
		}

		/* ------ METHODS ------ */

		/*-------------------------------------------------------------------*/
		/*                                                                   */
		/*                             GENERATE FP-TREE                      */
		/*                                                                   */
		/*-------------------------------------------------------------------*/  

		/* CREATE FP-TREE */   
		/// <summary>
		/// Top level method to commence the construction of the FP-Tree. </summary>

		public virtual void createFPtree()
		{
		//System.out.println("GENERATING FP-TREE\n------------------");

		// Create header table	
		headerTable = new FPgrowthHeaderTable[numOneItemSets + 1];

		// Populate header table	
		for (int index = 1;index < headerTable.Length;index++)
		{
			headerTable[index] = new FPgrowthHeaderTable(this, (short) index);
		}

		// Process datatable, loop through data table (stored in data array)
		// For each entry add the entry to the FP-tree.

		for (int index = 0;index < dataArray.Length;index++)
		{
			// Non null record (if initial data set has been reordered and
			// pruned some records may be empty
			if (dataArray[index] != null)
			{
				addToFPtree(rootNode,0,dataArray[index],1,headerTable);
			}
		}
		}

		/* ADD TO FP-TREE */   
		/// <summary>
		/// Searches through current list of child refs looking for given item set.
		/// <P> If reference for current itemset found increments support count and 
		/// proceed down branch, otherwise adds to current level. </summary>
		/// <param name="ref"> the current location in the FP-tree (<TT>rootNode</TT> at start). </param>
		/// <param name="place"> the current index in the given itemset. </param>
		/// <param name="itemSet"> the given itemset. </param>
		/// <param name="support"> the associated support value for the given itemset. </param>
		/// <param name="headerRef"> the link to the appropriate place in the header table.  </param>

		private void addToFPtree(FPtreeNode @ref, int place, short[] itemSet, int support, FPgrowthHeaderTable[] headerRef)
		{
		if (place < itemSet.Length)
		{
			if (!addToFPtree1(@ref,place,itemSet,support,headerRef))
			{
					addToFPtree2(@ref,place,itemSet,support,headerRef);
			}
		}
		}

		/* ADD TO FP TREE 1 */    
		/// <summary>
		/// Searches through existing branch and if itemset found updates the 
		/// support count and returns true, otherwise return false. </summary>
		/// <param name="ref"> the current FP-tree node reference. </param>
		/// <param name="place"> the current index in the given itemset. </param>
		/// <param name="itemSet"> the given itemset. </param>
		/// <param name="support"> the associated support value for the given itemset. </param>
		/// <param name="headerRef"> the link to the appropriate place in the header table. </param>
		/// <returns> true if given itemset exists in FP-tree, and false otherwise.  </returns>

		private bool addToFPtree1(FPtreeNode @ref, int place, short[] itemSet, int support, FPgrowthHeaderTable[] headerRef)
		{

		// Loop	
		if (@ref.childRefs != null)
		{
			for (int index = 0;index < @ref.childRefs.Length;index++)
			{
				// If item is already in list of child refs
				// increment count and proceed down branch.
				if (itemSet[place] == @ref.childRefs[index].node.itemName)
				{
					@ref.childRefs[index].node.itemCount = @ref.childRefs[index].node.itemCount + support;
				numUpdates++;
				addToFPtree(@ref.childRefs[index],place+1,itemSet,support, headerRef);
				return (true);
				}
				// Child refs ordered lexicographically so break when passed
			// point where item should be
			if (itemSet[place] < @ref.childRefs[index].node.itemName)
			{
						return (false);
			}
			}
		}

		// Default

		return (false);
		}

		/* ADD TO FP TREE 2 */

		/// <summary>
		/// Adds new node to FP-tree. <P> Adds first attribute in itemSet and then 
		/// rest of sequence. </summary>
		/// <param name="ref"> the current FP-tree node reference. </param>
		/// <param name="place"> the current index in the given itemset. </param>
		/// <param name="itemSet"> the given itemset. </param>
		/// <param name="support"> the associated support value for the given itemset. </param>
		/// <param name="headerRef"> the link to the appropriate place in the header table.  </param>

		private void addToFPtree2(FPtreeNode @ref, int place, short[] itemSet, int support, FPgrowthHeaderTable[] headerRef)
		{

		// Create new Item Prefix Subtree Node
		FPgrowthItemPrefixSubtreeNode newPrefixNode = new FPgrowthItemPrefixSubtreeNode(this, itemSet[place],support,@ref.node);
		// Create new FP tree node incorporating new Item Prefix Subtree Node
		FPtreeNode newFPtreeNode = new FPtreeNode(this, newPrefixNode);
		// Add link from header table
		addRefToFPgrowthHeaderTable(itemSet[place],newPrefixNode,headerRef);
		// Add into FP tree
		@ref.childRefs = reallocFPtreeChildRefs(@ref.childRefs,newFPtreeNode);
		// Proceed down branch with rest of itemSet
		addRestOfitemSet(@ref.childRefs[tempIndex],newPrefixNode,place+1,itemSet, support,headerRef);
		}

		/* ADD REST OF ITEMSET */

		/// <summary>
		/// Continues adding attributes in current itemset to FP-tree. </summary>
		/// <param name="ref"> the current FP-tree node reference. </param>
		/// <param name="backRef"> the backwards link to the previous node. </param>
		/// <param name="place"> the current index in the given itemset. </param>
		/// <param name="itemSet"> the given itemset. </param>
		/// <param name="support"> the associated support value for the given itemset. </param>
		/// <param name="headerRef"> the link to the appropriate place in the header table.  </param>

		private void addRestOfitemSet(FPtreeNode @ref, FPgrowthItemPrefixSubtreeNode backRef, int place, short[] itemSet, int support, FPgrowthHeaderTable[] headerRef)
		{

		// Process if more items in item set.
		if (place < itemSet.Length)
		{
			// Create new Item Prefix Subtree Node
			FPgrowthItemPrefixSubtreeNode newPrefixNode = new FPgrowthItemPrefixSubtreeNode(this, itemSet[place],support,backRef);
			// Create new FP tree node incorporating new Item Prefix Subtree 
			// Node
			FPtreeNode newFPtreeNode = new FPtreeNode(this, newPrefixNode);
			// Add link from header table
			addRefToFPgrowthHeaderTable(itemSet[place],newPrefixNode,headerRef);
			@ref.childRefs = reallocFPtreeChildRefs(@ref.childRefs,newFPtreeNode);
			// Add into FP tree
			addRestOfitemSet(@ref.childRefs[tempIndex],newPrefixNode,place+1, itemSet,support,headerRef);
		}
		}

		/* ADD REF TO HEADER TABLE */

		/// <summary>
		/// Adds reference to new FP-tree node to header table moving old reference 
		/// so that it becomes a link from the new FP-tree node. </summary>
		/// <param name="columnNumber"> the given attribute. </param>
		/// <param name="newNode"> the newly created FP-tree node. </param>
		/// <param name="headerRef"> the reference to the header table (array).  </param>

		private void addRefToFPgrowthHeaderTable(short columnNumber, FPgrowthItemPrefixSubtreeNode newNode, FPgrowthHeaderTable[] headerRef)
		{
			FPgrowthItemPrefixSubtreeNode tempRef;

		// Loop through header table
		for (int index = 1;index < headerRef.Length;index++)
		{
			// Found right attribute in table?
			if (columnNumber == headerRef[index].itemName)
			{
				tempRef = headerRef[index].nodeLink;
			headerRef[index].nodeLink = newNode;
			newNode.nodeLink = tempRef;
			break;
			}
		}
		}

		/* ---------------------------------------------------------- */
		/*                                                            */
		/*                       FP-TREE MINING                       */
		/*                                                            */
		/* ---------------------------------------------------------- */

		/* Methodology:
	
		1) Step through header table from end to start (least common single 
		attribute to most common single attribute). For each item.
		a) Count support by following node links and add to linked list of 
		   supported sets.
		b) Determine the "ancestor trails" connected to the nodes linked to the
		   current item in the header table.
		c) Treat the list of ancestor itemSets as a new set of input data and 
		   create a new header table based on the accumulated supported counts of 
		   the single items in the ancestor itemSets 
		d) Prune the ancestor itemSets so as to remove unsupported items.
		e) Repeat (1) with local header table and list of pruned ancestor itemSets 
		   as input */

		/* START MINING */

		/// <summary>
		/// Top level "FP-growth method" to mine the FP tree. </summary>

		public virtual void startMining()
		{

		Console.WriteLine("Mining FP-tree");

			startMining(headerTable,null);

		// Generate ARs
		generateARs();
		}

		/* START MINING */

		/// <summary>
		/// Commences process of mining the FP tree. <P> Commence with the bottom 
		/// of the header table and work upwards. Working upwards from the bottom of 
		/// the header table if there is a link to an FP tree node :
		/// <OL>
		/// <LI> Count the support.
		/// <LI> Build up itemSet sofar.
		/// <LI> Add to supported sets.
		/// <LI> Build a new FP tree: (i) create a new local root, (ii) create a 
		/// new local header table and (iii) populate with ancestors.
		/// <LI> If new local FP tree is not empty repeat mining operation.
		/// </OL>
		/// Otherwise end. </summary>
		/// <param name="tableRef"> the reference to the current location in the header table
		/// (commencing with the last item). </param>
		/// <param name="itemSetSofar"> the label fot the current item sets as generated to
		/// date (null at start).  </param>

		private void startMining(FPgrowthHeaderTable[] tableRef, short[] itemSetSofar)
		{
			int headerTableEnd = tableRef.Length - 1;
		FPgrowthColumnCounts[] countArray = null;
		FPgrowthHeaderTable[] localHeaderTable = null;
		FPtreeNode localRoot;
		int support;
		short[] newCodeSofar;

		// Loop through header table from end to start, item by item

			for (int index = headerTableEnd;index >= 1;index--)
			{
			// Check for null link
			if (tableRef[index].nodeLink != null)
			{
				// process trail of links from header table element
				startMining(tableRef[index].nodeLink,tableRef[index].itemName, itemSetSofar);
			}
			}
		}

		/// <summary>
		/// Commence process of mining FP tree with respect to a single element in
		/// the header table. </summary>
		/// <param name="nodeLink"> the firsty link from the header table pointing to an FP-tree
		/// node. </param>
		/// <param name="itemName"> the label associated with the element of interest in the 
		/// header table. </param>
		/// <param name="itemSetSofar"> the item set represented by the current FP-tree.  </param>

		public virtual void startMining(FPgrowthItemPrefixSubtreeNode nodeLink, short itemName, short[] itemSetSofar)
		{

			// Count support for current item in header table and store a
		// T-tree data structure
		int support = genSupHeadTabItem(nodeLink);
		short[] newCodeSofar = realloc2(itemSetSofar,itemName);
		addToTtree(newCodeSofar,support);

		// Collect ancestor itemSets and store in linked list structure 
		startTempSets = null;
		generateAncestorCodes(nodeLink);

		// Process Ancestor itemSets
		if (startTempSets != null)
		{
			// Count singles in linked list
			FPgrowthColumnCounts[] countArray = countFPgrowthSingles();
			// Create and populate local header table
			FPgrowthHeaderTable[] localHeaderTable = createLocalHeaderTable(countArray);
			if (localHeaderTable != null)
			{
			// Prune ancestor itemSets
			pruneAncestorCodes(countArray);
				// Create new local root for local FP tree
				FPtreeNode localRoot = generateLocalFPtree(localHeaderTable);
			// Mine new FP tree
			startMining(localHeaderTable,newCodeSofar);
			}
		}
		}

		/* ---------------------------------------------------------------------- */
		/*                                                                        */
		/*                     PROCESS CURRENT HEADER TABLE                       */
		/*                                                                        */
		/* ---------------------------------------------------------------------- */  

		/* GENERATE SUPPORT FOR HEADER TABLE SINGLE ITEM: */

		/// <summary>
		/// Counts support for single attributes in header table by following node 
		/// links. </summary>
		/// <param name="nodeLink"> the start link from the header table. </param>
		/// <returns> the support valye for the item set indicated by the header table.  </returns>

		private int genSupHeadTabItem(FPgrowthItemPrefixSubtreeNode nodeLink)
		{
			int counter = 0;

		// Loop

			while (nodeLink != null)
			{
			counter = counter + nodeLink.itemCount;
			numUpdates++;
			nodeLink = nodeLink.nodeLink;
			}

		// Return

		return (counter);
		}

		/* ---------------------------------------------------------------------- */
		/*                                                                        */
		/*                              ANCESTOR CODES                            */
		/*                                                                        */
		/* ---------------------------------------------------------------------- */  

		/* GENERATE ANCESTOR CODES */

		/// <summary>
		/// Generates ancestor itemSets are made up of the parent nodes of a given 
		/// node. This method collects such itemSets and stores them in a linked list 
		/// pointed at by startTempSets. </summary>
		/// <param name="ref"> the reference to the current node in the prefix tree containing
		/// itemsets together with support values. </param>

		private void generateAncestorCodes(FPgrowthItemPrefixSubtreeNode @ref)
		{
			short[] ancestorCode = null;
		int support;

		// Loop

			while (@ref != null)
			{
			support = @ref.itemCount;
			ancestorCode = getAncestorCode(@ref.parentRef);
			// Add to linked list with current support
			if (ancestorCode != null)
			{
				startTempSets = new FPgrowthSupportedSets(this, ancestorCode,support, startTempSets);
			}
			// Next ref	
			@ref = @ref.nodeLink;
			}
		}

		/* GET ANCESTOR CODE */

		/// <summary>
		/// Generate the ancestor itemSet from a given node. </summary>
		/// <param name="ref"> the reference to the current node in the prefix tree containing
		/// itemsets together with support values.  </param>

		private short[] getAncestorCode(FPgrowthItemPrefixSubtreeNode @ref)
		{
			short[] itemSet = null;

		if (@ref == null)
		{
			return (null);
		}

		// Else process

		while (@ref != null)
		{
			itemSet = realloc2(itemSet,@ref.itemName);
			@ref = @ref.parentRef;
		}

		// Return

		return (itemSet);
		}

		/* PRUNE ANCESTOR CODES */

		/// <summary>
		/// Removes elements in ancestor itemSets (pointed at by 
		/// <TT>startTempSets</TT>) which are not supported by referring to count 
		/// array (which contains all the current supported 1 itemsets). </summary>
		/// <param name="countArray"> the array of <TT>FPgrowthColumnCounts</TT> structures 
		/// describing the single item sets (in terms of labels and associated 
		/// support), contained in a linked list of <TT>FPgrowthSupportedSets</TT>
		/// which in turn describe the ancestor nodes in an FP-tree that preceed the 
		/// nodes identified by following a trail of links from a particular item in 
		/// the header table.     </param>

		private void pruneAncestorCodes(FPgrowthColumnCounts[] countArray)
		{
		FPgrowthSupportedSets @ref = startTempSets;

		// Loop through linked list of ancestor paths

		while (@ref != null)
		{
			for (int index = 0;index < @ref.itemSet.Length;index++)
			{
				if (countArray[@ref.itemSet[index]].support < minSupport)
				{
				  @ref.itemSet = removeElementN(@ref.itemSet,index);
				}
			}
			@ref = @ref.nodeLink;
		}
		}

		/* ---------------------------------------------------------------------- */
		/*                                                                        */
		/*      CREATE NEW HEADER TABLE FROM SINGLE ITEMS IN ANCESTOR CODES       */
		/*                                                                        */
		/* ---------------------------------------------------------------------- */  

		/* COUNT SINGLES */

		/// <summary>
		/// Counts frequent 1 item sets in ancestor itemSets linked list and place 
		/// into an array. </summary>
		/// <returns> array of <TT>FPgrowthColumnCounts</TT> structures describing the
		/// single item sets (in terms of labels and associated support), contained in 
		/// a linked list of <TT>FPgrowthSupportedSets</TT> which in turn describe the 
		/// ancestor nodes in an FP-tree that preceed the nodes identified by following 
		/// a trail of links from a particular item in the header table.  </returns>

		private FPgrowthColumnCounts[] countFPgrowthSingles()
		{
			int index , place = 0;
		FPgrowthSupportedSets nodeLink = startTempSets; // Start of linked list

		// Dimension array, assume all attributes present, then it will
		// be possible to index in to the array.

		FPgrowthColumnCounts[] countArray = new FPgrowthColumnCounts[numOneItemSets + 1];

		// Initialise array

		for (index = 1;index < numOneItemSets + 1;index++)
		{
			countArray[index] = new FPgrowthColumnCounts(this, index);
		}

		// Loop through linked list of ancestor itemSets

		while (nodeLink != null)
		{
			// Loop through itemSet 
			for (index = 0;index < nodeLink.itemSet.Length;index++)
			{
			place = nodeLink.itemSet[index];
			countArray[place].support = countArray[place].support + nodeLink.support;
			numUpdates++;
			}
			nodeLink = nodeLink.nodeLink;
		}

		// Return

		return (countArray);
		}

		/* CREATE LOCAL HEADER TABLE */

		/// <summary>
		/// Creates a local header table comprising those item that are supported 
		/// in the count array. </summary>
		/// <param name="countArray"> the support for the 1 item sets. </param>
		/// <returns> a FPgrowth header table.  </returns>

		private FPgrowthHeaderTable[] createLocalHeaderTable(FPgrowthColumnCounts[] countArray)
		{
			int index;
		FPgrowthHeaderTable[] localHeaderTable;

		localHeaderTable = localHeadTabUnordered(countArray);

		// Order according single item support

			//orderLocalHeaderTable(localHeaderTable,countArray);

		// Return

		return (localHeaderTable);
		}

		/* CREATE NEW LOCAL HEADER TABLE (UNORDERED) */

		/// <summary>
		/// Creatwx a new local header table, but unorderd. </summary>
		/// <param name="countArray"> the csupport for the 1 item sets. </param>
		/// <returns> a FPgrpwth header table.  </returns>

		private FPgrowthHeaderTable[] localHeadTabUnordered(FPgrowthColumnCounts[] countArray)
		{
			int counter = 1;

		// Loop through array and count supported one item sets	 
		for (int index = 1;index < countArray.Length;index++)
		{
			if (countArray[index].support >= minSupport)
			{
				counter++;
			}
		}

		// Build new Header Table array containing only supported items

		if (counter == 1)
		{
			return (null);
		}
		FPgrowthHeaderTable[] localHeaderTable = new FPgrowthHeaderTable[counter];

		// Populate header table

		int place = 1;
		for (int index = 1;index < countArray.Length;index++)
		{
			if (countArray[index].support >= minSupport)
			{
				localHeaderTable[place] = new FPgrowthHeaderTable(this, (short) countArray[index].columnNum);
				place++;
			}
		}

		// Return

		return (localHeaderTable);
		}

		/* ORDER LOCAL HEADER TABLE */

		/// <summary>
		/// Orders local header table (currently unused). </summary>
		/// <param name="localHeaderTable"> the FPgrpwth header table to be ordered. </param>
		/// <param name="countArray"> the csupport for the 1 item sets.  </param>

		private void orderLocalHeaderTable(FPgrowthHeaderTable[] localHeaderTable, FPgrowthColumnCounts[] countArray)
		{
		bool isOrdered;
		FPgrowthHeaderTable temp;
		int index, place1, place2;

		//loop through table
			do
			{
				index = 1;
			isOrdered = true;
			while (index < (localHeaderTable.Length - 1))
			{
				place1 = localHeaderTable[index].itemName;
					place2 = localHeaderTable[index + 1].itemName;
					if (countArray[place1].support > countArray[place2].support)
					{
					isOrdered = false;
				// Swap
						temp = localHeaderTable[index];
					localHeaderTable[index] = localHeaderTable[index + 1];
						localHeaderTable[index + 1] = temp;
					}
			// increment index
			index++;
			}
			} while (isOrdered == false);
		}

		/* ---------------------------------------------------------------------- */
		/*                                                                        */
		/*                         GENERATE NEW FP-TREE                           */
		/*                                                                        */
		/* ---------------------------------------------------------------------- */  

		/* GENERATE LOCAL FP-tree */

		/// <summary>
		/// Generates a local FP tree </summary>
		/// <param name="tableRef"> reference to start of header table containing links to
		/// an FP-tree produced during the FP-tree generation process.
		/// @rerurn reference to the start of the generated FP-tree </param>

		private FPtreeNode generateLocalFPtree(FPgrowthHeaderTable[] tableRef)
		{
			 FPgrowthSupportedSets @ref = startTempSets;
		 FPtreeNode localRoot = new FPtreeNode(this);

		 // Loop

			while (@ref != null)
			{
			// Add to conditional FP tree   
			if (@ref.itemSet != null)
			{
				addToFPtree(localRoot,0,@ref.itemSet, @ref.support,tableRef);
			}
				   @ref = @ref.nodeLink;
			}

		// Return

		return (localRoot);
		}

		/* ---------------------------------------------------------- */
		/*                                                            */
		/*                     FP-TREE UTILITIES                      */
		/*                                                            */
		/* ---------------------------------------------------------- */

		/* REALLOC 1 FP-TREE */

		/// <summary>
		/// Resizes the given array of FP-tree nodes so that its length is 
		/// increased by one element and new element inserted. </summary>
		/// <param name="oldArray"> the given array of FP-tree nodes. </param>
		/// <param name="newNode"> the given node to be added to the FP-tree </param>
		/// <returns> The revised array of FP-tree nodes.  </returns>

		private FPtreeNode[] reallocFPtreeChildRefs(FPtreeNode[] oldArray, FPtreeNode newNode)
		{

		// No old array

		if (oldArray == null)
		{
			FPtreeNode[] newArray = new FPtreeNode[] {newNode};
			tempIndex = 0;
			return (newArray);
		}

		// Otherwise create new array with length one greater than old array

		int oldArrayLength = oldArray.Length;
		FPtreeNode[] newArray2 = new FPtreeNode[oldArrayLength + 1];

		// Insert new node in correct lexicographic order.

		for (int index1 = 0;index1 < oldArrayLength;index1++)
		{
			if (newNode.node.itemName < oldArray[index1].node.itemName)
			{
			newArray2[index1] = newNode;
			for (int index2 = index1;index2 < oldArrayLength;index2++)
			{
				newArray2[index2 + 1] = oldArray[index2];
			}
			tempIndex = index1;
			return (newArray2);
			}
			newArray2[index1] = oldArray[index1];
		}

		// Default

		newArray2[oldArrayLength] = newNode;
		tempIndex = oldArrayLength;
		return (newArray2);
		}

		/*------------------------------------------------------------------ */
		/*                                                                   */
		/*                           OUTPUT METHODS                          */
		/*                                                                   */
		/*------------------------------------------------------------------ */

		/* OUTPUT HEADER TABLE */

		/// <summary>
		/// Commences process of outputting the prefix sub tree to the screen, 
		/// starting at header table. 
		/// </summary>

		public virtual void outputItemPrefixSubtree()
		{
			int flag;
			Console.WriteLine("PREFIX SUBTREE FROM HEADER TABLE");
			for (int index = 1;index < headerTable.Length;index++)
			{
			Console.WriteLine("Header = " + reconvertItem(headerTable[index].itemName));
			flag = outputItemPrefixTree(headerTable[index].nodeLink);
			if (flag != 1)
			{
				Console.WriteLine();
			}
			}
		Console.WriteLine();
		}

		/// <summary>
		/// Commences process of outputting a local prefix sub tree to the screen. </summary>
		/// <param name="tableRef"> the reference to the local header table.  </param>

		private void outputItemPrefixSubtree(FPgrowthHeaderTable[] tableRef)
		{
			int flag;
			Console.WriteLine("PREFIX SUBTREE FROM LOCAL HEADER TABLE");
			for (int index = 1;index < tableRef.Length;index++)
			{
			Console.WriteLine("Header = " + reconvertItem(tableRef[index].itemName));
			flag = outputItemPrefixTree(tableRef[index].nodeLink);
			if (flag != 1)
			{
				Console.WriteLine();
			}
			}
		Console.WriteLine();
		}

		/// <summary>
		/// Outputs the given prefix sub tree. </summary>
		/// <param name="ref"> the reference to the given branch. </param>
		/// <returns> a counter representing the current "node number" (used in 
		/// output).  </returns>

		private int outputItemPrefixTree(FPgrowthItemPrefixSubtreeNode @ref)
		{
			int counter = 1;

		// Loop

		while (@ref != null)
		{
				Console.Write("(" + counter + ") " + (reconvertItem(@ref.itemName)) + ":" + @ref.itemCount + " ");
			counter++;
			@ref = @ref.nodeLink;
		}

		return (counter);
		}

		/* OUTPUT FP TREE */

		/// <summary>
		/// Commences process of outputting FP-tree to screen. </summary>

		public virtual void outputFPtree()
		{
			Console.WriteLine("FP TREE");
		outputFPtreeNode1();
			Console.WriteLine();
		}

		/// <summary>
		/// Commences process of outputting a given branch of an FP-tree to the
		/// screen. </summary>
		/// <param name="ref"> the reference to the given FP-tree branch.  </param>

		private void outputFPtreeNode(FPtreeNode @ref)
		{
			Console.WriteLine("LOCAL FP TREE");
		outputFPtreeNode2(@ref.childRefs,"");
			Console.WriteLine();
		}

		/// <summary>
		/// Continues process of outputting FP-tree to screen. </summary>

		private void outputFPtreeNode1()
		{
		outputFPtreeNode2(rootNode.childRefs,"");
		}

		/// <summary>
		/// Outputs a given level in an FP-tree to the screen. </summary>
		/// <param name="ref"> the reference to the given FP-tree level. </param>
		/// <param name="nodeID"> the root string for the node ID.  </param>

		private void outputFPtreeNode2(FPtreeNode[] @ref, string nodeID)
		{
			if (@ref == null)
			{
				return;
			}

		// Otherwise process

			for (int index = 0;index < @ref.Length;index++)
			{
			Console.Write("(" + nodeID + (index + 1) + ") ");
			outputItemPrefixSubtreeNode(@ref[index].node);
			outputFPtreeNode2(@ref[index].childRefs,nodeID + (index + 1) + ".");
			}
		}

		/* OUTPUT ITEM PREFIX SUB-TREE NODE	*/

		/// <summary>
		/// Outputs the given prefix sub tree node. </summary>
		/// <param name="ref"> the reference to the given node.  </param>

		public virtual void outputItemPrefixSubtreeNode(FPgrowthItemPrefixSubtreeNode @ref)
		{
			Console.Write((reconvertItem(@ref.itemName)) + ":" + @ref.itemCount);
		if (@ref.nodeLink != null)
		{
			Console.WriteLine(" (ref to " + (reconvertItem(@ref.nodeLink.itemName)) + ":" + @ref.nodeLink.itemCount + ")");
		}
		else
		{
			Console.WriteLine(" (ref to null)");
		}
		}

		/* OUTPUT ANCESTER TRAIL */

		/// <summary>
		/// Commence the process of outputting the ancestor trail from the header 
		/// table 
		/// </summary>

		private void outputAncesterTrail()
		{
			int flag;
			Console.WriteLine("ANCESTOR TRAIL FROM HEADER TABLE");
			for (int index = 1;index < headerTable.Length;index++)
			{
			Console.WriteLine("Header = " + (reconvertItem(headerTable[index].itemName)));
			outputAncestorTrail1(headerTable[index].nodeLink);
			}
		Console.WriteLine();
		}

		/// <summary>
		/// Commence the process of outputting the ancestor trail from a local
		/// header table. </summary>
		/// <param name="tableRef"> the reference to the local header table.  </param>

		private void outputAncesterTrail(FPgrowthHeaderTable[] tableRef)
		{
			int flag;
			Console.WriteLine("ANCESTOR TRAIL FROM LOCAL HEADER TABLE");
			for (int index = 1;index < tableRef.Length;index++)
			{
			Console.WriteLine("Header = " + (reconvertItem(tableRef[index].itemName)));
			outputAncestorTrail1(tableRef[index].nodeLink);
			}
		Console.WriteLine();
		}

		/// <summary>
		/// Outputs the ancestor trail given a prefix sub tree. </summary>
		/// <param name="ref"> the reference to the given branch.  </param>

		private void outputAncestorTrail1(FPgrowthItemPrefixSubtreeNode @ref)
		{
		while (@ref != null)
		{
			Console.Write("\t");
				outputAncestorTrail2(@ref);
			@ref = @ref.nodeLink;
			Console.WriteLine();
		}
		}

		/// <summary>
		/// Outputs the given ancestor trail node in prefix sub tree. </summary>
		/// <param name="ref"> the reference to the given node.  </param>

		private void outputAncestorTrail2(FPgrowthItemPrefixSubtreeNode @ref)
		{
		while (@ref != null)
		{
			Console.Write("(" + (reconvertItem(@ref.itemName)) + ":" + @ref.itemCount + ") ");
			@ref = @ref.parentRef;
		}
		}

		/* OUTPUT FP TREE STORAGE: */

		/// <summary>
		/// Commence process of determining and outputting FP-tree storage, number 
		/// of updates and number of nodes. 
		/// </summary>

		public virtual void outputFPtreeStorage()
		{
			int storage = 8; // 8 Bytes for root node
		numberOfNodes = 1; // For root node
		storage = calculateStorage(rootNode.childRefs,storage);

		// Add header table.

		storage = storage + (headerTable.Length * 6);
		Console.WriteLine("FP tree storage = " + storage + " (bytes)");
		Console.WriteLine("FP tree updates = " + numUpdates);
		Console.WriteLine("FP tree nodes   = " + numberOfNodes);
		}

		/* CALCULATE STORAGE */

		/// <summary>
		/// Determines storage requirements for FP-tree. </summary>
		/// <param name="ref"> the reference to the current portion of the P-tree under
		/// consideration. </param>
		/// <param name="storage"> the storage requirements so far. </param>
		/// <returns> the storage in Bytes required for the given FP=tree node. </returns>

		private int calculateStorage(FPtreeNode[] @ref, int storage)
		{
		if (@ref == null)
		{
			return (storage);
		}

		// Process, each node has 14+8 bytes of storage, 8 for FP tree
		// links (child and sibling), 14 for prefix tree links (parentRef, 
		// nodeRef, Support, ID

			for (int index = 0;index < @ref.Length;index++)
			{
			storage = storage + 14 + 8;
			numberOfNodes++;
			storage = calculateStorage(@ref[index].childRefs,storage);
			}

		// Return

		return (storage);
		}

		/* OUTPUT LOCAL ARRAY COUNT */

		/// <summary>
		/// Output local array count structure (diagnostic use only). </summary>
		/// <param name="countArray"> the array of <TT>FPgrowthColumnCounts</TT> structures 
		/// describing the single item sets (in terms of labels and associated 
		/// support), contained in a linked list of <TT>FPgrowthSupportedSets</TT>
		/// which in turn describe the ancestor nodes in an FP-tree that preceed the 
		/// nodes identified by following a trail of links from a particular item in 
		/// the header table.   </param>

		private void outputColumnCount(FPgrowthColumnCounts[] countArray)
		{

		for (int index = 1;index < countArray.Length;index++)
		{
			Console.Write("Col " + countArray[index].columnNum + " : ");
			if (countArray[index].support == 0)
			{
							Console.WriteLine("Unsupported");
			}
			else
			{
				Console.WriteLine(countArray[index].support);
			}
		}
		Console.WriteLine();
		}

        private void InitializeComponent()
        {
            this.SuspendLayout();
            // 
            // FPtree
            // 
            this.ClientSize = new System.Drawing.Size(558, 287);
            this.Name = "FPtree";
            this.ResumeLayout(false);

        }
	}


}